#include "heap.h"

void heap_sort_down(typedata* arr, int size)
{
	//降序建小堆
	////*********************向上调整建堆************************//
	for (int i = 1; i <= size; i++)
	{
		HP_small_up(arr, i);
	}
	while (size)
	{
		//
		int tmp = arr[0];
		arr[0] = arr[size];
		arr[size] = tmp;
		//
		--size;
		adjust_down(arr, size);
	}
}


void heap_sort_up(typedata* arr, int size)
{
	//升序建大堆
	//for (int i = 0; i < size; i++)
	//{
	//	HP_big_up(arr, i);
	//}
	////*********************向下调整建堆************************//
	int tsize = (size - 1)/2;
	while (tsize!=-1)
	{
		int father = tsize;
		int child = father * 2 + 1;
		while (child <= size)
		{
			if (child + 1 <= size&&arr[child + 1] > arr[child])
			{
				++child;
			}
			if (arr[father] < arr[child])
			{
				int tmp = arr[father];
				arr[father] = arr[child];
				arr[child] = tmp;
			}
			father = child;
			child = father * 2 + 1;
		}
		--tsize;
	}
	while(size)
	{
		//
		int tmp = arr[0];
		arr[0] = arr[size];
		arr[size] = tmp;
		//
		--size;
		adjust_up(arr, size);
	}
}


int main()
{

	//HP hp;
	//HPinit(&hp);
	//HPpush_small(&hp, 27);
	//HPpush_small(&hp, 37);
	//HPpush_small(&hp, 28);
	//HPpush_small(&hp, 10);
	//HPpush_small(&hp, 15);
	//HPpush_small(&hp, 19);
	//HPpush_small(&hp, 25);
	//HPpush_small(&hp, 18);
	//HPpush_small(&hp, 65);
	//HPpush_small(&hp, 49);
	//HPpush_small(&hp, 34);
	//int i = 0;
	//for (i; i < hp.size; i++)
	//{
	//	printf("%d  ", hp.arr[i]);
	//}
	////打印有序
	//while (hp.size+1)
	//{
	//	printf("%d  ", HPpop_small(&hp));
	//}


	HP hp;
	HPinit(&hp);
	HPpush_big(&hp, 27);
	HPpush_big(&hp, 37);
	HPpush_big(&hp, 28);
	HPpush_big(&hp, 10);
	HPpush_big(&hp, 15);
	HPpush_big(&hp, 19);
	HPpush_big(&hp, 25);
	HPpush_big(&hp, 18);
	HPpush_big(&hp, 65);
	HPpush_big(&hp, 49);
	HPpush_big(&hp, 34);
	int i = 0;
	for (i; i < hp.size; i++)
	{
		printf("%d  ", hp.arr[i]);
	}
	printf("\n");
	int size = HP_Size(&hp);
	printf("size = % d\n", size);
	 int n = HP_Top(&hp);
	printf("  top=%d\n", n);
	//打印有序
	while (hp.size+1)
	{
		printf("%d  ", HPpop_small(&hp));
	}
	 if(HP_Empty(&hp))printf("\n _empty");
	 HP_Destory(&hp);

	//int arr[10] = { 5,6,7,1,2,3,4,9,8,0 };
	//int size = sizeof(arr) / sizeof(int);
	//heap_sort_up(arr, size);
	//for (int i = 0; i < 10; i++)printf("%d", arr[i]);


	//printf("\n");


	//int brr[10] = { 5,6,7,1,2,3,4,9,8,0 };
	//size = sizeof(brr) / sizeof(int);
	//heap_sort_down(brr, size);
	//for (int i = 0; i < 10; i++)printf("%d", brr[i]);

	return 0;
}